package leetcode.editor.cn;
//存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u]
// 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有
//以下属性：
//
// 
// 不存在自环（graph[u] 不包含 u）。 
// 不存在平行边（graph[u] 不包含重复值）。 
// 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图） 
// 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。 
// 
//
// 二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称
//为 二分图 。 
//
// 如果图是二分图，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
//输出：false
//解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。 
//
// 示例 2： 
// 
// 
//输入：graph = [[1,3],[0,2],[1,3],[0,2]]
//输出：true
//解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。 
//
// 
//
// 提示： 
//
// 
// graph.length == n 
// 1 <= n <= 100 
// 0 <= graph[u].length < n 
// 0 <= graph[u][i] <= n - 1 
// graph[u] 不会包含 u 
// graph[u] 的所有值 互不相同 
// 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 459 👎 0


import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution106 {

    // 访问过的接待你
    boolean[] visited;
    // 节点颜色，true、false代表两种颜色
    boolean[] color;
    // 结果
    boolean bipartite = true;


    /**
     * 二分图判断，给节点染色，相邻的两个节点颜色不能一致
     *
     * @param graph
     * @return
     */
    public boolean isBipartite(int[][] graph) {
        return isBipartiteByBFS(graph);
    }

    private boolean isBipartiteByDFS(int[][] graph) {
        color = new boolean[graph.length];
        visited = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                traverseByDFS(graph, i);
            }
        }
        return bipartite;
    }

    private void traverseByDFS(int[][] graph, int i) {
        if (!bipartite) {
            // 不是二分图
            return;
        }
        visited[i] = true;
        for (int next : graph[i]) {
            if (visited[next]) {
                if (color[i] == color[next]) {
                    // 相邻节点颜色相同,不是二分图
                    bipartite = false;
                    return;
                }
            } else {
                color[next] = !color[i];
                visited[next] = true;
                traverseByDFS(graph, next);
            }
        }
    }

    private boolean isBipartiteByBFS(int[][] graph) {
        visited = new boolean[graph.length];
        color = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                traverseByBFS(graph, i);
            }
        }
        return bipartite;
    }

    private void traverseByBFS(int[][] graph, int i) {
//        if (!bipartite) {
////            不是二分图
//            return;
//        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        visited[i] = true;
        while (!queue.isEmpty() && bipartite) {
            Integer curr = queue.poll();
            for (int next : graph[curr]) {
                if (visited[next]) {
                    if (color[curr] == color[next]) {
                        // 相邻节点颜色相同,不是二分图
                        bipartite = false;
                        return;
                    }
                } else {
                    color[next] = !color[curr];
                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }

    }

    public static void main(String[] args) {
        Solution106 solution106 = new Solution106();
        System.out.println(solution106.isBipartiteByBFS(new int[][]{{1, 3}, {0, 2}, {1, 3}, {0, 2}}));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
